#include "Joseph.h"
void initJosephGame(JosephHeader *game, int n) {
    Node *node;
    for (int i = 1; i <= n; ++i) {
        node = (Node *) malloc(sizeof(Node));
        node->data = i;
        node->next = NULL;
        if (game->head == NULL) {
            game->head = game->rear = node;
        } else {	// 尾插法
            game->rear->next = node;
            game->rear = node;
        }
    }
    game->rear->next = game->head;
}

// 不带头节点的循环链表遍历
void showData(JosephHeader *game) {
    Node *p = game->head;
    do {
        printf("%d\t", p->data);
        p = p->next;
    } while (p != game->head);
    printf("\n");
}

void startJosephGame(JosephHeader *game, int m) {
    // 数到了m的节点，要删除，要维护前后的关系，根据单向链表的特点
    // 数到m-1的时候，就能够触发删除m这个节点的行为
    Node *prev = NULL;				// 指向待删除节点的前一个位置
    Node *cur = game->head;			// 指向正在报数的人
    while (cur->next != cur) {		// 还有其他节点
        // 按照m值来报数，报到m-1
        prev = cur;
        for (int i = 1; i < m; ++i) {
            prev = cur;
            cur = cur->next;
        }
        // prev他的下一个就是要删除
        prev->next = cur->next;
        printf("%d\t", cur->data);
        free(cur);
        cur = prev->next;
    }
    printf("\nthe last person: %d\n", cur->data);
}